package com.bo.day20241113;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 输入: 正数数组costs、正数数组profits、正数K、正数M
 * costs[i]表示i号项目的花费
 * profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
 * K表示你只能串行的最多做k个项目
 * M表示你初始的资金
 * 说明: 每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
 * 输出：你最后获得的最大钱数。
 *
 * @Author: gpb
 * @Date: 2024/11/19 15:34
 * @Description:
 */
public class IPO {
    /**
     * 说明: 每做完一个项目，马上获得的收益，可以支持你去做下一个项目。不能并行的做项目。
     * 输出：你最后获得的最大钱数。
     * 解题思路：
     * 首先对项目的花费进行升序排序,放到小根堆中去
     * 循环K次，每次从堆中取出花费最小的项目，如果当前资金大于等于该项目花费，就从堆中取出
     * 放到大根堆中去,并且将大根堆中的利润最大的项目
     *
     * @param K       表示你只能串行的最多做k个项目
     * @param M       表示你初始的资金
     * @param Profits 表示i号项目在扣除花费之后还能挣到的钱(利润)
     * @param Capital 表示i号项目的花费
     * @return
     */
    public static int findMaximizedCapital (int K, int M, int[] Profits, int[] Capital) {
        PriorityQueue<Program> min = new PriorityQueue<>(new MinCostComparator());
        PriorityQueue<Program> max = new PriorityQueue<>(new MaxProfitComparator());
        // 遍历项目数组，将花费小于等于M的项目放入小根堆中
        for (int i = 0; i < Profits.length; i++) {
            min.add(new Program(Profits[i], Capital[i]));
        }
        // 循环K次，可以做个K个项目
        int i = 0;
        while (i < K) {
            // 能够做的项目
            while (!min.isEmpty() && min.peek().c <= M) {
                // 放到大根堆，安装利润降序排序
                max.add(min.poll());
            }
            // 如果大根堆为空，则无法做项目，返回当前资金
            if (max.isEmpty()) {
                return M;
            }
            // 从大根堆中取出利润最大的项目，并且将资金加上利润
            M += max.poll().p;
            i++;
        }
        return M;
    }

    public static class Program {
        public int p; // 利润
        public int c; // 花费

        public Program (int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    // 定义比较器, 按照花费从小到大排序
    public static class MinCostComparator implements Comparator<Program> {
        @Override
        public int compare (Program o1, Program o2) {
            return o1.c - o2.c;
        }
    }

    // 定义比较器, 按照利润从大到小排序
    public static class MaxProfitComparator implements Comparator<Program> {
        @Override
        public int compare (Program o1, Program o2) {
            return o2.p - o1.p;
        }
    }
}
